package _hash

import org.junit.Assert
import org.junit.Test

/**
 * https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html
 * https://leetcode.cn/problems/ransom-note/description/
 *
 * 383. 赎金信
 *
 * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
 * 如果可以，返回 true ；否则返回 false 。
 * magazine 中的每个字符只能在 ransomNote 中使用一次。
 *
 * 示例 1：
 *
 * 输入：ransomNote = "a", magazine = "b"
 * 输出：false
 * 示例 2：
 *
 * 输入：ransomNote = "aa", magazine = "ab"
 * 输出：false
 * 示例 3：
 *
 * 输入：ransomNote = "aa", magazine = "aab"
 * 输出：true
 */
class leetcode_383 {
    @Test
    fun test1() {
        val actual = canConstruct(ransomNote = "aa", magazine = "aab")
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    fun canConstruct(ransomNote: String, magazine: String): Boolean {
        /**
        map
        str1 -> char array
        str2 -> char array
        str1 : map +1
        str2 : map -1
        loop map < 0 : false
        true
         */

        val array: IntArray = IntArray('z' - 'a' + 1)
        val str1: CharArray = magazine.toCharArray()
        val str2: CharArray = ransomNote.toCharArray()
        for (ch in str1) {
            array[ch - 'a'] = array[ch - 'a'] + 1
        }

        for (ch in str2) {
            array[ch - 'a'] = array[ch - 'a'] - 1
        }

        for (n in array) {
            if (n < 0) {
                return false
            }
        }
        return true
    }
}